#include "main/utils.h"
using namespace std;

struct PrefixNode {
  int val = 0;
  PrefixNode* childern[26];
};

void insertNode(PrefixNode* root,
                const string& key,
                const int& value) {
  auto node = root;
  for (auto ch : key) {
    if (node->childern[ch - 'a'] == nullptr) {
      node->childern[ch - 'a'] = new PrefixNode();
    }
    node = node->childern[ch - 'a'];
  }
  node->val = value;
}

PrefixNode* buildPrefixTree(const vector<string>& key,
                            const vector<int>& value) {
  PrefixNode* root = new PrefixNode();
  for (int i = 0; i < key.size(); ++i) {
    insertNode(root, key[i], value[i]);
  }
  return root;
}

void dfs(PrefixNode* node, int& sum_length) {
  if (node->val) {
    sum_length += node->val;
    return;
  }
  for (int i = 0; i < 26; ++i) {
    if (node->childern[i]) {
      dfs(node->childern[i], sum_length);
    }
  }
}

int getSum(PrefixNode* node) {
  if (!node)
    return 0;

  int sum = node->val;
  for (auto child : node->childern) {
    sum += getSum(child);
  }
  return sum;
}

int sumOfWord(const vector<string>& key,
              const vector<int>& value,
              const string& target) {
  PrefixNode* root = buildPrefixTree(key, value);
  auto node = root;
  for (auto ch : target) {
    if (node->childern[ch - 'a']) {
      node = node->childern[ch - 'a'];
    } else {
      return -1;
    }
  }
  // int sum_length = 0;
  // dfs(node, sum_length);
  // return sum_length;
  return getSum(node);
}

int main() {
  vector<string> key = {"happy", "happen"};
  vector<int> value = {3, 2};
  string target = "ha";
  cout << sumOfWord(key, value, target) << endl;

  return 0;
}
